class Solution(object):
    def numDistinctIslands(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])
        islands = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    now_islands = []
                    now_islands.append((i, j))
                    now_set = [(i, j)]
                    while now_set:
                        next_set = []
                        for x, y in now_set:
                            for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                                if 0 <= ux < m and 0 <= uy < n and grid[ux][uy] == 1:
                                    grid[ux][uy] = 2
                                    next_set.append((ux, uy))
                        now_set = next_set
                        now_islands += now_set
                    min_x = min([item[0] for item in now_islands])
                    min_y = min([item[1] for item in now_islands])
                    now_islands = [(item[0] - min_x, item[1] - min_y) for item in now_islands]
                    now_islands.sort()
                    islands.add(tuple(now_islands))
        return len(islands)

data = Solution()
grid = [[1, 1, 1, 1], [1, 0, 1, 1], [0, 0, 0, 0], [0, 1, 1, 1], [1, 1, 0, 1]]
print(data.numDistinctIslands(grid))
grid = [[1, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 1], [0, 0, 0, 1, 1]]
print(data.numDistinctIslands(grid))
grid = [[0, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 1, 0]]
print(data.numDistinctIslands(grid))
grid = [[1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 1, 1]]
print(data.numDistinctIslands(grid))
grid = [[1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1], [1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0],
        [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0], [1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0],
        [0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1], [1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0],
        [1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0], [0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1],
        [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0], [1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1]]
print(data.numDistinctIslands(grid))



